# 深度优先搜索
# class Solution(object):
#     def numIslands(self, grid):
#         """
#         :type grid: List[List[str]]
#         :rtype: int
#
#         """
#         M = len(grid)
#         N = len(grid[0])
#         value = 0
#         already_set = set()
#
#         def search(i, j):
#             already_set.add((i, j))
#             if i - 1 >= 0:
#                 if grid[i - 1][j] == '1' and (i - 1, j) not in already_set:
#                     search(i - 1, j)
#             if i + 1 < M:
#                 if grid[i + 1][j] == '1' and (i + 1, j) not in already_set:
#                     search(i + 1, j)
#             if j - 1 >= 0:
#                 if grid[i][j - 1] == '1' and (i, j - 1) not in already_set:
#                     search(i, j - 1)
#             if j + 1 < N:
#                 if grid[i][j + 1] == '1' and (i, j + 1) not in already_set:
#                     search(i, j + 1)
#
#         for i in range(len(grid)):
#             for j in range(len(grid[0])):
#                 if grid[i][j] == '1' and (i, j) not in already_set:
#                     value += 1
#                     search(i, j)
#
#         return value

class Union:
    def __init__(self, grid):
        self.M = len(grid)
        self.N = len(grid[0])
        self.grid = grid
        self.parent = [-1] * self.M * self.N
        self.count = 0
        for i in range(self.M):
            for j in range(self.N):
                if grid[i][j] == '1':
                    self.parent[i * self.N + j] = i * self.N + j
                    self.count += 1

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def uf(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if root_x < root_y:
                self.parent[root_y] = root_x
            else:
                self.parent[root_x] = root_y
            self.count -= 1

    def union(self):
        for i in range(self.M):
            for j in range(self.N):
                if self.grid[i][j] == '1':
                    self.grid[i][j] = '0'
                    for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                        if 0 <= x < self.M and 0 <= y < self.N:
                            if self.grid[x][y] == '1':
                                self.uf(self.N * x + y, self.N * i + j)

    def getcount(self):
        self.union()
        return self.count

class Solution(object):
    def numIslands(self, grid):
        u = Union(grid)
        return u.getcount()


data = Solution()
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
print(data.numIslands(grid))
grid = [["1","1","1"],["0","1","0"],["1","1","1"]]
print(data.numIslands(grid))
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(data.numIslands(grid))